During the last few years, there is an ever increasing need for effective and reliable digital communication and data storage systems. This need has been enhanced by the usage of large and high-speed data networks for the exchange, processing and storage of digital information. One big issue related to the design of such systems is error correction to ensure error-free communication during data transmission.
FIG. 1 shows communication system 100 according to an exemplary embodiment. Information Source 110 provides Transmitter 120 with source data. Transmitter 120 includes Source Encoder 122 coupled to Channel Encoder 124 coupled to Modulator 126. Source Encoder 122 receives source data from information source 110 and encodes the source data to generate encoded data. Channel Encoder 124 receives encoded data from Source Encoder 122 and generates Channel data. Modulator 126 receives Channel data from Channel Encoder 124 and generates Modulated data. Modulated data is transmitted over Channel 130. Channel 130 may be a wireless or wired communication channel. Channel 130 is prone to noise. Noise is added to modulated data over Channel 130. Receiver 140 receives noisy data comprising modulated data and noise. Receiver 140 includes Demodulator 142 coupled to Channel Decoder 144 coupled to Source Decoder 146. Demodulator 142 receives the noisy data and demodulates the noisy data to generate demodulated data. Channel decoder 144 receives demodulated data from Demodulator 142 and generates Channel data. Source decoder 146 receives channel data from Channel Decoder 144. Source Decoder 146 decodes the channel data and generates the source data originally provided to Transmitter 120. Receiver 140 is coupled to Destination 150 to provide Destination 150 with the source data.
As is known by Shannon's code theory, it is possible to reduce the possibility of error reception through a noisy channel provided that the transmission rate does not exceed the channel capacity. More specifically, for a channel having bandwidth (B) and signal-to-noise ratio (SNR), the channel capacity (C), i.e. the maximum error-free transmission rate, in bits per second (BPS) is given by:C=B log2(1+SNR)  (Equation 1)
By properly encoding of data, errors can be minimized to whatever level is desired without reducing the transmission rate. Nevertheless, the lower the desired error rate is the more complex the required encoding shall be.
The purpose of channel encoding is to minimize the possibility of erroneous transmission. The error correcting code used as well as the encoding-decoding processes define to a large extent the system throughput. Error correcting codes are split into two large categories: Block Codes and Convolutional Codes.
Block Codes are characterized by the segmentation of data to be transmitted into K symbol length blocks and corresponding N symbol length blocks called codewords, where N≧K. A block code is considered linear if each linear combination of two codewords is also a codeword.
The transformation of a K bit length sequence (K data) to an N bit length sequence (codeword) is accomplished with the help of a K×N binary matrix called Generator Matrix (G). The code-word (ci) is generated by multiplying the K data with the matrix G.ci=uiG  (Equation 2)
Low-Density Parity Check (LDPC) codes are a subcategory of linear block codes. LDPC codes are characterized by an LDPC parity check matrix (H) and a corresponding Tanner graph. Decoding is performed through an iterative process of information exchange between two processing unit types.
For LDPC codes an LDPC matrix H must fulfil the following equation:ciHT=0  (Equation 3)
An LDPC code having a Parity Check matrix with equal number of non-zero components for each row (du) and for each column (dc) of the matrix, respectively, is called a regular LDPC code.
FIG. 2 shows a small-scale example of a parity check matrix (H) of a regular LDPC code. Each column and row of the matrix comprises an equal number of elements of value of either one or zero.
FIG. 3 depicts the relation of the H matrix with the corresponding Tanner graph 300 by means of an example. Rows in matrix H correspond to Check Nodes, marked as squares, while columns in matrix H correspond to Variable Nodes, marked as circles in the Tanner graph 300. The code depicted is a (9, 2, 3)-LDPC code. There are 9 columns in H, each column having 2 “1”s and each row 3 “1”s, respectively. The 9 variable nodes and the 6 Check Nodes in the Tanner diagram represent the 9 columns and the 6 rows of H, respectively. The connections represent the “1”s.
LDPC code design techniques are divided into two categories: (i) random code construction and (ii) structured code construction. LDPC matrices designed with a random code construction technique have no limitation as to their structure. Good random codes have a performance close to the theoretical Shannon limit. However, an encoder-decoder system based on such a code requires high die area and complex connectivity due to the lack of structure of the matrix H. On the other hand, structured LDPC codes are based on specific arithmetic structures. As a consequence, the structure of the matrix may be exploited to achieve low complexity and less die area as well as linear-time encoding and parallel encoding/decoding processes.
A sub-category of structured LDPC codes are the Quasi-Cyclic LDPC codes.
FIG. 4 depicts an example parity-check matrix H composed of circularly shifted identity sub-matrices. Nonzero elements (ones) are represented as dots. Zeros are not shown. The variable degrees that appear in the particular matrix are also shown. LDPC codes the parity check matrix of which has this structure are the Quasi-Cyclic LDPC codes (QC-LDPC). QC-LDPC codes are comprised of square sub-matrices of size z. Each sub-matrix is either a z×z zero sub-matrix or a z×z identity sub-matrix with a right circulant shifting factor having a value of s.
FIG. 5 depicts a compressed representation of a parity-check matrix corresponding to a quasi-cyclic LDPC code. In the particular example minus one represents an all zero z×z matrix, while nonnegative integers are shift factors, applied to z×z identity matrices in order to derive the actual parity check matrix, which is of the structure depicted in FIG. 4. In this example, the codeword length N=2304, z=96 and the code rate R=½.
QC-LDPC codes are used widely in present LDPC encoding-decoding systems. QC-LDPC codes have prevailed as they demand low die area both for the encoder and the decoder. The complexity of the encoding procedure is not dependant only on the algorithm employed but also in the memory management during storage of the H matrix. A reduction in the required storage memory leads to a reduction in required hardware. Thus lower die area is accomplished.
Storage management of the matrix H is a significant contributor to lower die area, however, the compression method should not increase the difficulty in the encoding process. The use of other assets for translating the compressed information may lead to additional hardware or extra clock cycles which is not desirable.
One known way to deal with memory management and decoding speed is to exploit the parallel encoding/decoding capabilities of QC LDPC codes. This can be achieved by having more than one levels of parallelism. However, this results in circuits that are more die intensive. Therefore there is a need for a design technique that optimizes the management of the trade-off between decoding speed and hardware complexity.